"""
Copyright 2007, Thomas Dejanovic.
 
This is free software; you can redistribute it and/or modify it
under the terms of the GNU Lesser General Public License as
published by the Free Software Foundation; either version 2.1 of
the License, or (at your option) any later version.
 
This software is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
 
You should have received a copy of the GNU Lesser General Public
License along with this software; if not, write to the Free
Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
02110-1301 USA, or see the FSF site: http://www.fsf.org.

This module defines iterators for hatch node trees that are useful 
throughout hatch. 
"""

id = "$Id: hatch_iterators.py 667 2010-07-01 00:12:17Z jayshurtz $"
# $URL: http://hatch.googlecode.com/svn/tags/taggle_release_2.2/hatch/hatch_library/hatch_iterators.py $
# $Author: jayshurtz $
version = " ".join(id.split()[1:3])


import to_hatch_structure
from hatch_constants import CHILDNODES_ATTRIBUTE, PARENT_ATTRIBUTE
from hatch_constants import NAME_ATTRIBUTE, PROPERTIES_ATTRIBUTE


class HatchNodeIteratorDepthFirst(object):
    """ Depth first iterator for trees composed of HatchNode or similiarly 
        styled classes (ie: any class for which the CHILDNODES_ATTRIBUTE exists 
        and is iterable, and the __getattribute__ method exists.)
    """
    def __init__(self, hatchNode):
        self.stack = [hatchNode]
    def __iter__(self):
        return self
    def next(self):
        if len(self.stack) == 0:
            raise StopIteration
        hatchNode = self.stack.pop(-1)
        childNodes = hatchNode.__getattribute__(CHILDNODES_ATTRIBUTE)
        for index in xrange(len(childNodes)-1, -1, -1): # Add to stack in REVERSE order.
            self.stack.append(childNodes[index])
        return hatchNode

class HatchNodeIteratorBreadthFirst(object):
    """ Breadth first iterator for trees composed of HatchNode or similiarly 
        styled classes (ie: any class for which the CHILDNODES_ATTRIBUTE exists
        and is iterable, and the __getattribute__ method exists.)
    """
    def __init__(self, hatchNode):
        self.queue = [hatchNode]
    def __iter__(self):
        return self
    def next(self):
        if len(self.queue) == 0:
            raise StopIteration
        hatchNode = self.queue.pop(0)
        childNodes = hatchNode.__getattribute__(CHILDNODES_ATTRIBUTE)
        for child in childNodes:
            self.queue.append(child)
        return hatchNode


# TODO Bottom-up iterators ?


# For testing.
if __name__ == "__main__":

    from hatch_node import HatchNode

    #       h6
    #      /  \
    #     h5   h4
    #    /  \    \
    #   h1   h2   h3
    #  /  \
    # h7   h0
    h0 = HatchNode('h0')
    h7 = HatchNode('h7')
    h1 = HatchNode('h1', h0, h7)
    h2 = HatchNode('h2')
    h3 = HatchNode('h3')
    h4 = HatchNode('h4', h3)
    h5 = HatchNode('h5', h2, h1)
    h6 = HatchNode('h6', h5, h4)


    for node in HatchNodeIteratorBreadthFirst(h6):
        print node.name
    print "\n"

    print ", ".join([node.name for node in HatchNodeIteratorDepthFirst(h6)])
    print "\n"

    iterator = HatchNodeIteratorBreadthFirst(h5)
    done = False
    node = iterator.next()
    while not done:
        print node.name
        try:
            node = iterator.next()
        except StopIteration:
            done = True
    print "\n"


